The recent increase in popularity of the World Wide Web (WWW or web) has lead to a considerable increase in the amount of traffic over the Internet. As a result, the web has now become one of the primary bottlenecks on network performance. When documents are requested by a user who is connected to a server via a slow network link, there can be noticeable latency at the user end. Further, transferring the document over the network leads to an increase in the level of traffic over the network. This reduces the bandwidth available for other requests. In order to reduce access latencies, it is desirable to store (cache) copies of popular documents closer to the user, from which the access latencies are more acceptable.
The cache can be implemented at various points on the network. For example, a large university or corporation may have its own local cache, from which all the users subscribing to that network may fetch documents. It is often desirable to implement specialized servers in the network, called caching proxies, which act as agents on the behalf of the client in order to locate the cached copy of a document. Usually caching proxies serve as secondary or higher level caches, because they are concerned only with misses not available on client caches. Client caches are built into the web browsers, and may either store only the document accesses during the current invocation (nonpersistent cache such as Mosaic) or may cache documents across invocations.
One prior art caching method is called the least recently used (LRU) method. In LRU, a list of the objects is maintained in the cache and is ordered based on decreasing frequency of access. In other words the most recently accessed object is the first in the list, while the least recently accessed object is at the bottom. When a new object is accessed, one or more objects may have to be pruned from the list to make room in the cache for the most recently accessed object. Thus, this method does not take size into account in its cache replacement process.
Another important issue is admission control; i.e., when to allow an object to enter the cache at all. It may not always be favorable to insert an object into the cache, because it may lower the probability of a hit to the cache. For two objects which are equally frequently accessed, the cache hit ratio is maximized when the replacement policy is biased towards documents of smaller size. This is because it is possible to store a greater number of smaller size documents. While deciding which documents to replace when a new object enters, both the relative frequency of access, and the size of the objects should be taken into account.
In Abrams M., Standridge C. R., Abdulla G., Williams S., and Fox E. A., "Caching Proxies: Limitations and Potentials. Fourth International World Wide Web Conference Proceedings", Abrams et al., [ABRAMS] discuss some cache replacement policies which do take size into account in the decision making process. The following are two of the policies discussed:
(1) LRU (LRU-THOLD) thresholding policy: In this case, a threshold size is specified, above which no object may be cached. For the purpose of replacement, a pure LRU policy may be used. Thus, this scheme uses size for the purpose of admission control only; while the replacement policy still follows pure LRU replacement; i.e., when an object is to be admitted to the cache, the objects in the list which were the least recently accessed are pruned to make room for the incoming object.
(2) LRU-MIN policy: This policy tries to minimize the number of documents replaced. Let the size of the incoming object be S. If there are any objects in the cache which have a size which is at least S, then remove that object from the cache based on LRU order. On the other hand, if there are no objects with size at least S, then consider objects of size at least S/2, and so on until enough free cache space has been created.
ABRAMS concludes that the LRU-MIN is preferable over most workloads, since (unlike LRU-THOLD) there are no parameters to be chosen. It achieves generally better performance, even when optimal thresholds are used for the LRU-THOLD policy. In fact, the optimal value of the thresholds to be used for the LRU-THOLD policy depend upon the nature and type of the underlying data, which may vary from one application to another.